package zhr.os;

import java.util.ArrayList;
import java.util.Arrays;

public class BankerAlgorithm {
    private int numOfResources; // 资源类型的数量
    private int[] available; // 可用资源数组
    private int[][] max; // 每个进程的最大需求数组
    private int[][] allocation; // 每个进程的已分配资源数组
    private int[][] need; // 每个进程还需要的资源数组

    public BankerAlgorithm(int numOfResources, int[] available, int[][] max, int[][] allocation) {
        this.numOfResources = numOfResources;
        this.available = available;
        this.max = max;
        this.allocation = allocation;
        this.need = new int[allocation.length][numOfResources];
        for (int i = 0; i < allocation.length; i++) {
            for (int j = 0; j < numOfResources; j++) {
                need[i][j] = max[i][j] - allocation[i][j];
            }
        }
    }

    // 检查请求是否有效
    private boolean isRequestValid(int[] request, int processID) {
        for (int i = 0; i < numOfResources; i++) {
            if (request[i] > need[processID][i]) {
                System.out.println("进程 " + processID + " 请求的资源超过其最大需求");
                return false;
            }
            if (request[i] > available[i]) {
                System.out.println("进程 " + processID + " 请求的资源超过可用资源");
                return false;
            }
        }
        return true;
    }

    // 尝试分配资源并检查是否安全
    private boolean isSafeState() {
        boolean[] finish = new boolean[allocation.length];
        int[] work = available.clone();
        int safeSequence[] = new int[allocation.length];

        // 查找至少一个进程能满足条件
        for (int count = 0; count < allocation.length; count++) {
            for (int i = 0; i < allocation.length; i++) {
                if (!finish[i]) {
                    boolean canAllocate = true;
                    for (int j = 0; j < numOfResources; j++) {
                        need[i][count] = max[i][j] - allocation[i][j];
                        if (need[i][j] > work[j]) {
                            canAllocate = false;
                            break;
                        }
                    }
                    if (canAllocate) {
                        for (int k = 0; k < numOfResources; k++) {
                            work[k] += allocation[i][k];
                        }
                        safeSequence[count] = i;
                        finish[i] = true;
                    }
                }
            }
        }

        // 如果所有进程都完成，则算法安全
        for (boolean b : finish) {
            if (!b) {
                return false;
            }
        }
        return true;
    }

    // 请求资源
    public boolean requestResources(int processID, int[] request) {
        if (isRequestValid(request, processID)) {
            for (int i = 0; i < numOfResources; i++) {
                available[i] -= request[i];
                allocation[processID][i] += request[i];
                need[processID][i] -= request[i];
            }
            if (isSafeState()) {
                System.out.println("请求被批准，系统处于安全状态");
                return true;
            } else {
                // 回滚
                for (int i = 0; i < numOfResources; i++) {
                    available[i] += request[i];
                    allocation[processID][i] -= request[i];
                    need[processID][i] += request[i];
                }
                System.out.println("请求被拒绝，系统不处于安全状态");
                return false;
            }
        } else {
            System.out.println("请求无效");
            return false;
        }
    }

    // 打印当前状态
    public void printState() {
        System.out.println("最大需求: ");
        for (int i = 0; i < max.length; i++) {
            System.out.println("P" + i + ": " + java.util.Arrays.toString(max[i]));
        }
        System.out.println("已分配资源: ");
        for (int i = 0; i < allocation.length; i++) {
            System.out.println("P" + i + ": " + java.util.Arrays.toString(allocation[i]));
        }
        System.out.println("还需要的资源: ");
        for (int i = 0; i < need.length; i++) {
            System.out.println("P" + i + ": " + java.util.Arrays.toString(need[i]));
        }
    }

    // 找安全序列
    public int[] findSafeSequence() {
        int[] work = available.clone(); // 可用资源工作
        boolean[] finish = new boolean[allocation.length]; // 标记进程是否完成
        int[] safeSequence = new int[allocation.length]; // 安全序列
        int count = 0; // 用于记录安全序列中进程的数量
        ArrayList<Integer> processes = new ArrayList<>();
        for (int i = 0; i < allocation.length; i++) {
            processes.add(i);
        }
        while (!processes.isEmpty()) {
            boolean found = false;
            for (int i : processes) {
                // 检查进程i是否有足够的资源继续运行
                boolean canAllocate = true;
                for (int j = 0; j < numOfResources; j++) {
                    if (need[i][j] > work[j]) {
                        canAllocate = false;
                        break;
                    }
                }
                if (canAllocate) {
                    // 假设分配资源给进程i并释放
                    System.out.println("--------------------");
                    System.out.println("进程"+i+"执行并释放");
                    for (int k = 0; k < numOfResources; k++) {
                        work[k] += allocation[i][k];
                    }
                    safeSequence[count++] = i; // 将进程i加入安全序列
                    finish[i] = true; // 标记进程i为完成
                    processes.remove(Integer.valueOf(i)); // 从列表中移除进程i
                    found = true;
                    System.out.println("可用资源"+Arrays.toString(work));
                    break; // 找到可以运行的进程后，跳出循环
                }
            }
            if (!found) {
                throw new IllegalStateException("无法找到安全序列，系统可能不安全");
            }
        }
        return safeSequence;
    }
}